package com.cn.codebrush.动态规划;

/**
 * @Author Boolean
 * @Date 2022/5/14 17:40
 * @Version 1.0
 */
public class No213打家劫舍II {
    public static void main(String[] args) {
        int[] nums= {2,3,2};
        int[] nums1= {1,2,3,1};
        int[] nums2 = {1,3,1,3,100};
        int[] nums3 = {6,3,10,8,2,10,3,5,10,5,3};
        System.out.println(rob(nums3));
    }

    public static int rob(int[] nums) {
        int n = nums.length;
        int v1 = robHelper(nums,0,n-2);
        int v2 = robHelper(nums,1,n-1);
        return Math.max(v1,v2);
    }

    public static int robHelper(int[] nums,int start,int end) {
        int n = end-start+1;
        if(n == 1){
            return nums[start];
        }
        int[] dp = new int[n];
        dp[0] = nums[start];
        dp[1] = Math.max(nums[start+1],nums[start]);
        for(int i=2;i<n;i++){
            dp[i] = Math.max(dp[i-2]+nums[start+i],dp[i-1]);
        }
        return Math.max(dp[n-1],dp[n-2]);
    }
}
